package org.example.myleet.p873;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int maxLen = 0;
        Map<Integer, Integer> numberMapIndex = new HashMap<>(arr.length);
        for (int i = 0; i < arr.length; ++i) {
            numberMapIndex.put(arr[i], i);
        }
        //assume k < j < i
        int[][] dp = new int[arr.length][arr.length];
        for (int j = 0; j < arr.length; ++j) {
            for (int i = j + 1; i < arr.length; ++i) {
                int x = arr[i] - arr[j];
                if (x >= arr[j]) {
                    continue;
                }
                Integer k = numberMapIndex.get(x);
                if (null != k) {
                    //found arr[k] == arr[i] - arr[j]
                    dp[i][j] = Math.max(3, dp[j][k] + 1);
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }

    //非动态规划，直接暴力扫描斐波那契数列
//    public int lenLongestFibSubseq(int[] arr) {
//        int maxLen = 0;
//        Map<Integer, Integer> numberMapIndex = new HashMap<>(arr.length);
//        for (int i = 0; i < arr.length; ++i) {
//            numberMapIndex.put(arr[i], i);
//        }
//        int end = arr[arr.length - 1];
//        for (int i = 0; i < arr.length; ++i) {
//            for (int j = i + 1; j < arr.length; ++j) {
//                int f1 = arr[i];
//                int f2 = arr[j];
//                int seq2 = 2;
//                do {
//                    int f3 = f1 + f2;
//                    int seq3 = seq2 + 1;
//                    Integer idx = numberMapIndex.get(f3);
//                    if (null != idx) {
//                        maxLen = Math.max(maxLen, seq3);
//                    } else {
//                        break;
//                    }
//                    f1 = f2;
//                    f2 = f3;
//                    ++seq2;
//                } while (f2 <= end);
//            }
//        }
//        return maxLen;
//    }
}
